﻿
/**
 * DLS (Depth-limited search)
 */
public class DLS
{
    /**
     * Problem description
     */
    protected UndirectedGraph mGraph;

    /**
     * Constructor
     */
    public DLS(string fn)
    {
        mGraph = new UndirectedGraph();
        mGraph.readInProblem(fn);
    }

    /**
     * Generic sceleton for search on the problem
     */
    public System.Collections.Generic.List<Node> depthLimitedSearch(string initialState, string goalState, int limit)
    {
        /** setup graph for search */
        mGraph.setupProblem(initialState, goalState);
        Node source = mGraph.findNode(initialState);
        
        /** return RECURSIVE-DLS(MAKE-NODE(INITIAL-STATE[problem]), problem, limit) */
        return recursiveDLS(source, limit);
     }

    protected System.Collections.Generic.List<Node> recursiveDLS(Node node, int limit)
    {
        /** cutoff_occurered? <- false */
        
        /** if GOAL-TEST[problem](STATE[node]) then return SOLUTION(node)
         *  else if DEPTH[node] = limit then return cutoff
         *  else for each successor in EXPAND(node, problem) do
         *      result <- RECURSIVE-DLS(successor, problem, limit)
         *      if result = cutoff then cutoff_occurered? <- true
         *      else if result != failure then return result
         *  if cutoff_occurred? then return cutoff else return failure
         */
        if (mGraph.isGoal(node)) {
            return constructPathByNode(node);
        } else if (node.getDepth() == limit) {
            return null;
        } else {
            System.Collections.Generic.List<Node> successors = generic_expand(node);
            System.Collections.Generic.List<Node> result = null;
            foreach (Node s in successors) {
                result = recursiveDLS(s, limit);
                if (result != null) { return result; }
            }
        }
        return null;
    }



    /**
     * Get Path by a node
     */
    public System.Collections.Generic.List<Node> constructPathByNode(Node node)
    {
        System.Collections.Generic.List<Node> result = new System.Collections.Generic.List<Node>();

        /** current node */
        Node current = node;

        /** construct path */
        do
        {
            result.Add(current);
            current = current.getParent();
        } while (current != null);

        /** reverse order */
        result.Reverse();

        /** return constructed path */
        return result;
    }


    /**
     * expands a node and returns list of chosen new nodes
     */
    public System.Collections.Generic.List<Node> generic_expand(Node parent)
    {
        /** successors <- the empty set */
        System.Collections.Generic.List<Node> result = new System.Collections.Generic.List<Node>();

        /**
         * for each <action, result> in SUCCESSOR-FN[problem](STATE[node]) do
         *      s <- a new NODE
         *      STATE[s] <- result
         *      PARENT-NODE[s] <- node
         *      ACTION[s] <- action
         *      PATH-COST[s] <- PATH-COST[node] + STEP-COST(node, action, s)
         *      DEPTH[s] <- DEPTH[node] + 1
         *      add s to successors
         * return successors
         */
        foreach (System.Tuple<Edge, Node> tuple in mGraph.getSuccessors(parent))
        {
            Edge edge = tuple.Item1;
            Node child = tuple.Item2;
            child.setParent(parent);
            child.setPredecessorEdge(edge);
            child.setPathCost(parent.getPathCost() + edge.getStepCost());
            child.setDepth(parent.getDepth() + 1);
            result.Add(child);
        }

        return result;
    }

    /** to implement by specific search strategy */
    

} // class DLS

